<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html lang="en">

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
  <title>LCOV - mbi.info - detail/binary_search.hpp</title>
  <link rel="stylesheet" type="text/css" href="../gcov.css">
</head>

<body>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="title">LTP GCOV extension - code coverage report</td></tr>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>

    <tr>
      <td width="100%">
        <table cellpadding=1 border=0 width="100%">
        <tr>
          <td class="headerItem" width="20%">Current&nbsp;view:</td>
          <td class="headerValue" width="80%" colspan=4><a href="../index.html">directory</a> - <a href="index.html">detail</a> - binary_search.hpp</td>
        </tr>
        <tr>
          <td class="headerItem" width="20%">Test:</td>
          <td class="headerValue" width="80%" colspan=4>mbi.info</td>
        </tr>
        <tr>
          <td class="headerItem" width="20%">Date:</td>
          <td class="headerValue" width="20%">2010-01-23</td>
          <td width="20%"></td>
          <td class="headerItem" width="20%">Instrumented&nbsp;lines:</td>
          <td class="headerValue" width="20%">13</td>
        </tr>
        <tr>
          <td class="headerItem" width="20%">Code&nbsp;covered:</td>
          <td class="headerValue" width="20%">100.0 %</td>
          <td width="20%"></td>
          <td class="headerItem" width="20%">Executed&nbsp;lines:</td>
          <td class="headerValue" width="20%">13</td>
        </tr>
        </table>
      </td>
    </tr>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
  </table>

  <table cellpadding=0 cellspacing=0 border=0>
    <tr>
      <td><br></td>
    </tr>
    <tr>
      <td><pre class="source">
<span class="lineNum">       1 </span>                : // Copyright (c)  2000 David Abrahams. 
<span class="lineNum">       2 </span>                : // Distributed under the Boost Software License, Version 1.0. 
<span class="lineNum">       3 </span>                : // (See accompanying file LICENSE_1_0.txt or copy at 
<span class="lineNum">       4 </span>                : // http://www.boost.org/LICENSE_1_0.txt)
<span class="lineNum">       5 </span>                : // 
<span class="lineNum">       6 </span>                : // Copyright (c) 1994
<span class="lineNum">       7 </span>                : // Hewlett-Packard Company
<span class="lineNum">       8 </span>                : // 
<span class="lineNum">       9 </span>                : // Permission to use, copy, modify, distribute and sell this software
<span class="lineNum">      10 </span>                : // and its documentation for any purpose is hereby granted without fee,
<span class="lineNum">      11 </span>                : // provided that the above copyright notice appear in all copies and
<span class="lineNum">      12 </span>                : // that both that copyright notice and this permission notice appear
<span class="lineNum">      13 </span>                : // in supporting documentation.  Hewlett-Packard Company makes no
<span class="lineNum">      14 </span>                : // representations about the suitability of this software for any
<span class="lineNum">      15 </span>                : // purpose.  It is provided &quot;as is&quot; without express or implied warranty.
<span class="lineNum">      16 </span>                : // 
<span class="lineNum">      17 </span>                : // Copyright (c) 1996
<span class="lineNum">      18 </span>                : // Silicon Graphics Computer Systems, Inc.
<span class="lineNum">      19 </span>                : // 
<span class="lineNum">      20 </span>                : // Permission to use, copy, modify, distribute and sell this software
<span class="lineNum">      21 </span>                : // and its documentation for any purpose is hereby granted without fee,
<span class="lineNum">      22 </span>                : // provided that the above copyright notice appear in all copies and
<span class="lineNum">      23 </span>                : // that both that copyright notice and this permission notice appear
<span class="lineNum">      24 </span>                : // in supporting documentation.  Silicon Graphics makes no
<span class="lineNum">      25 </span>                : // representations about the suitability of this software for any
<span class="lineNum">      26 </span>                : // purpose.  It is provided &quot;as is&quot; without express or implied warranty.
<span class="lineNum">      27 </span>                : // 
<span class="lineNum">      28 </span>                : #ifndef BINARY_SEARCH_DWA_122600_H_
<span class="lineNum">      29 </span>                : # define BINARY_SEARCH_DWA_122600_H_
<span class="lineNum">      30 </span>                : 
<span class="lineNum">      31 </span>                : # include &lt;boost/detail/iterator.hpp&gt;
<span class="lineNum">      32 </span>                : # include &lt;utility&gt;
<span class="lineNum">      33 </span>                : 
<span class="lineNum">      34 </span>                : namespace boost { namespace detail {
<span class="lineNum">      35 </span>                : 
<span class="lineNum">      36 </span>                : template &lt;class ForwardIter, class Tp&gt;
<span class="lineNum">      37 </span>                : ForwardIter lower_bound(ForwardIter first, ForwardIter last,
<span class="lineNum">      38 </span>                :                              const Tp&amp; val) 
<span class="lineNum">      39 </span>                : {
<span class="lineNum">      40 </span>                :     typedef detail::iterator_traits&lt;ForwardIter&gt; traits;
<span class="lineNum">      41 </span>                :     
<span class="lineNum">      42 </span>                :     typename traits::difference_type len = boost::detail::distance(first, last);
<span class="lineNum">      43 </span>                :     typename traits::difference_type half;
<span class="lineNum">      44 </span>                :     ForwardIter middle;
<span class="lineNum">      45 </span>                : 
<span class="lineNum">      46 </span>                :     while (len &gt; 0) {
<span class="lineNum">      47 </span>                :       half = len &gt;&gt; 1;
<span class="lineNum">      48 </span>                :       middle = first;
<span class="lineNum">      49 </span>                :       std::advance(middle, half);
<span class="lineNum">      50 </span>                :       if (*middle &lt; val) {
<span class="lineNum">      51 </span>                :         first = middle;
<span class="lineNum">      52 </span>                :         ++first;
<span class="lineNum">      53 </span>                :         len = len - half - 1;
<span class="lineNum">      54 </span>                :       }
<span class="lineNum">      55 </span>                :       else
<span class="lineNum">      56 </span>                :         len = half;
<span class="lineNum">      57 </span>                :     }
<span class="lineNum">      58 </span>                :     return first;
<span class="lineNum">      59 </span>                : }
<span class="lineNum">      60 </span>                : 
<span class="lineNum">      61 </span>                : template &lt;class ForwardIter, class Tp, class Compare&gt;
<span class="lineNum">      62 </span><span class="lineCov">             42 : ForwardIter lower_bound(ForwardIter first, ForwardIter last,</span>
<span class="lineNum">      63 </span>                :                               const Tp&amp; val, Compare comp)
<span class="lineNum">      64 </span>                : {
<span class="lineNum">      65 </span>                :   typedef detail::iterator_traits&lt;ForwardIter&gt; traits;
<span class="lineNum">      66 </span>                : 
<span class="lineNum">      67 </span><span class="lineCov">             42 :   typename traits::difference_type len = boost::detail::distance(first, last);</span>
<span class="lineNum">      68 </span>                :   typename traits::difference_type half;
<span class="lineNum">      69 </span><span class="lineCov">             42 :   ForwardIter middle;</span>
<span class="lineNum">      70 </span>                : 
<span class="lineNum">      71 </span><span class="lineCov">            250 :   while (len &gt; 0) {</span>
<span class="lineNum">      72 </span><span class="lineCov">            166 :     half = len &gt;&gt; 1;</span>
<span class="lineNum">      73 </span><span class="lineCov">            166 :     middle = first;</span>
<span class="lineNum">      74 </span><span class="lineCov">            166 :     std::advance(middle, half);</span>
<span class="lineNum">      75 </span><span class="lineCov">            166 :     if (comp(*middle, val)) {</span>
<span class="lineNum">      76 </span><span class="lineCov">             62 :       first = middle;</span>
<span class="lineNum">      77 </span><span class="lineCov">             62 :       ++first;</span>
<span class="lineNum">      78 </span><span class="lineCov">             62 :       len = len - half - 1;</span>
<span class="lineNum">      79 </span>                :     }
<span class="lineNum">      80 </span>                :     else
<span class="lineNum">      81 </span><span class="lineCov">            104 :       len = half;</span>
<span class="lineNum">      82 </span>                :   }
<span class="lineNum">      83 </span><span class="lineCov">             42 :   return first;</span>
<span class="lineNum">      84 </span>                : }
<span class="lineNum">      85 </span>                : 
<span class="lineNum">      86 </span>                : template &lt;class ForwardIter, class Tp&gt;
<span class="lineNum">      87 </span>                : ForwardIter upper_bound(ForwardIter first, ForwardIter last,
<span class="lineNum">      88 </span>                :                            const Tp&amp; val)
<span class="lineNum">      89 </span>                : {
<span class="lineNum">      90 </span>                :   typedef detail::iterator_traits&lt;ForwardIter&gt; traits;
<span class="lineNum">      91 </span>                : 
<span class="lineNum">      92 </span>                :   typename traits::difference_type len = boost::detail::distance(first, last);
<span class="lineNum">      93 </span>                :   typename traits::difference_type half;
<span class="lineNum">      94 </span>                :   ForwardIter middle;
<span class="lineNum">      95 </span>                : 
<span class="lineNum">      96 </span>                :   while (len &gt; 0) {
<span class="lineNum">      97 </span>                :     half = len &gt;&gt; 1;
<span class="lineNum">      98 </span>                :     middle = first;
<span class="lineNum">      99 </span>                :     std::advance(middle, half);
<span class="lineNum">     100 </span>                :     if (val &lt; *middle)
<span class="lineNum">     101 </span>                :       len = half;
<span class="lineNum">     102 </span>                :     else {
<span class="lineNum">     103 </span>                :       first = middle;
<span class="lineNum">     104 </span>                :       ++first;
<span class="lineNum">     105 </span>                :       len = len - half - 1;
<span class="lineNum">     106 </span>                :     }
<span class="lineNum">     107 </span>                :   }
<span class="lineNum">     108 </span>                :   return first;
<span class="lineNum">     109 </span>                : }
<span class="lineNum">     110 </span>                : 
<span class="lineNum">     111 </span>                : template &lt;class ForwardIter, class Tp, class Compare&gt;
<span class="lineNum">     112 </span>                : ForwardIter upper_bound(ForwardIter first, ForwardIter last,
<span class="lineNum">     113 </span>                :                            const Tp&amp; val, Compare comp)
<span class="lineNum">     114 </span>                : {
<span class="lineNum">     115 </span>                :   typedef detail::iterator_traits&lt;ForwardIter&gt; traits;
<span class="lineNum">     116 </span>                : 
<span class="lineNum">     117 </span>                :   typename traits::difference_type len = boost::detail::distance(first, last);
<span class="lineNum">     118 </span>                :   typename traits::difference_type half;
<span class="lineNum">     119 </span>                :   ForwardIter middle;
<span class="lineNum">     120 </span>                : 
<span class="lineNum">     121 </span>                :   while (len &gt; 0) {
<span class="lineNum">     122 </span>                :     half = len &gt;&gt; 1;
<span class="lineNum">     123 </span>                :     middle = first;
<span class="lineNum">     124 </span>                :     std::advance(middle, half);
<span class="lineNum">     125 </span>                :     if (comp(val, *middle))
<span class="lineNum">     126 </span>                :       len = half;
<span class="lineNum">     127 </span>                :     else {
<span class="lineNum">     128 </span>                :       first = middle;
<span class="lineNum">     129 </span>                :       ++first;
<span class="lineNum">     130 </span>                :       len = len - half - 1;
<span class="lineNum">     131 </span>                :     }
<span class="lineNum">     132 </span>                :   }
<span class="lineNum">     133 </span>                :   return first;
<span class="lineNum">     134 </span>                : }
<span class="lineNum">     135 </span>                : 
<span class="lineNum">     136 </span>                : template &lt;class ForwardIter, class Tp&gt;
<span class="lineNum">     137 </span>                : std::pair&lt;ForwardIter, ForwardIter&gt;
<span class="lineNum">     138 </span>                : equal_range(ForwardIter first, ForwardIter last, const Tp&amp; val)
<span class="lineNum">     139 </span>                : {
<span class="lineNum">     140 </span>                :   typedef detail::iterator_traits&lt;ForwardIter&gt; traits;
<span class="lineNum">     141 </span>                : 
<span class="lineNum">     142 </span>                :   typename traits::difference_type len = boost::detail::distance(first, last);
<span class="lineNum">     143 </span>                :   typename traits::difference_type half;
<span class="lineNum">     144 </span>                :   ForwardIter middle, left, right;
<span class="lineNum">     145 </span>                : 
<span class="lineNum">     146 </span>                :   while (len &gt; 0) {
<span class="lineNum">     147 </span>                :     half = len &gt;&gt; 1;
<span class="lineNum">     148 </span>                :     middle = first;
<span class="lineNum">     149 </span>                :     std::advance(middle, half);
<span class="lineNum">     150 </span>                :     if (*middle &lt; val) {
<span class="lineNum">     151 </span>                :       first = middle;
<span class="lineNum">     152 </span>                :       ++first;
<span class="lineNum">     153 </span>                :       len = len - half - 1;
<span class="lineNum">     154 </span>                :     }
<span class="lineNum">     155 </span>                :     else if (val &lt; *middle)
<span class="lineNum">     156 </span>                :       len = half;
<span class="lineNum">     157 </span>                :     else {
<span class="lineNum">     158 </span>                :       left = boost::detail::lower_bound(first, middle, val);
<span class="lineNum">     159 </span>                :       std::advance(first, len);
<span class="lineNum">     160 </span>                :       right = boost::detail::upper_bound(++middle, first, val);
<span class="lineNum">     161 </span>                :       return std::pair&lt;ForwardIter, ForwardIter&gt;(left, right);
<span class="lineNum">     162 </span>                :     }
<span class="lineNum">     163 </span>                :   }
<span class="lineNum">     164 </span>                :   return std::pair&lt;ForwardIter, ForwardIter&gt;(first, first);
<span class="lineNum">     165 </span>                : }
<span class="lineNum">     166 </span>                : 
<span class="lineNum">     167 </span>                : template &lt;class ForwardIter, class Tp, class Compare&gt;
<span class="lineNum">     168 </span>                : std::pair&lt;ForwardIter, ForwardIter&gt;
<span class="lineNum">     169 </span>                : equal_range(ForwardIter first, ForwardIter last, const Tp&amp; val,
<span class="lineNum">     170 </span>                :               Compare comp)
<span class="lineNum">     171 </span>                : {
<span class="lineNum">     172 </span>                :   typedef detail::iterator_traits&lt;ForwardIter&gt; traits;
<span class="lineNum">     173 </span>                : 
<span class="lineNum">     174 </span>                :   typename traits::difference_type len = boost::detail::distance(first, last);
<span class="lineNum">     175 </span>                :   typename traits::difference_type half;
<span class="lineNum">     176 </span>                :   ForwardIter middle, left, right;
<span class="lineNum">     177 </span>                : 
<span class="lineNum">     178 </span>                :   while (len &gt; 0) {
<span class="lineNum">     179 </span>                :     half = len &gt;&gt; 1;
<span class="lineNum">     180 </span>                :     middle = first;
<span class="lineNum">     181 </span>                :     std::advance(middle, half);
<span class="lineNum">     182 </span>                :     if (comp(*middle, val)) {
<span class="lineNum">     183 </span>                :       first = middle;
<span class="lineNum">     184 </span>                :       ++first;
<span class="lineNum">     185 </span>                :       len = len - half - 1;
<span class="lineNum">     186 </span>                :     }
<span class="lineNum">     187 </span>                :     else if (comp(val, *middle))
<span class="lineNum">     188 </span>                :       len = half;
<span class="lineNum">     189 </span>                :     else {
<span class="lineNum">     190 </span>                :       left = boost::detail::lower_bound(first, middle, val, comp);
<span class="lineNum">     191 </span>                :       std::advance(first, len);
<span class="lineNum">     192 </span>                :       right = boost::detail::upper_bound(++middle, first, val, comp);
<span class="lineNum">     193 </span>                :       return std::pair&lt;ForwardIter, ForwardIter&gt;(left, right);
<span class="lineNum">     194 </span>                :     }
<span class="lineNum">     195 </span>                :   }
<span class="lineNum">     196 </span>                :   return std::pair&lt;ForwardIter, ForwardIter&gt;(first, first);
<span class="lineNum">     197 </span>                : }           
<span class="lineNum">     198 </span>                : 
<span class="lineNum">     199 </span>                : template &lt;class ForwardIter, class Tp&gt;
<span class="lineNum">     200 </span>                : bool binary_search(ForwardIter first, ForwardIter last,
<span class="lineNum">     201 </span>                :                    const Tp&amp; val) {
<span class="lineNum">     202 </span>                :   ForwardIter i = boost::detail::lower_bound(first, last, val);
<span class="lineNum">     203 </span>                :   return i != last &amp;&amp; !(val &lt; *i);
<span class="lineNum">     204 </span>                : }
<span class="lineNum">     205 </span>                : 
<span class="lineNum">     206 </span>                : template &lt;class ForwardIter, class Tp, class Compare&gt;
<span class="lineNum">     207 </span>                : bool binary_search(ForwardIter first, ForwardIter last,
<span class="lineNum">     208 </span>                :                    const Tp&amp; val,
<span class="lineNum">     209 </span>                :                    Compare comp) {
<span class="lineNum">     210 </span>                :   ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
<span class="lineNum">     211 </span>                :   return i != last &amp;&amp; !comp(val, *i);
<span class="lineNum">     212 </span>                : }
<span class="lineNum">     213 </span>                : 
<span class="lineNum">     214 </span>                : }} // namespace boost::detail
<span class="lineNum">     215 </span>                : 
<span class="lineNum">     216 </span>                : #endif // BINARY_SEARCH_DWA_122600_H_
</pre>
      </td>
    </tr>
  </table>
  <br>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
  <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
  <tr><td class="versionInfo">Generated by: <a href="http://ltp.sourceforge.net/coverage/lcov.php" target="_parent">LTP GCOV extension version 1.6</a></td></tr>
  </table>
  <br>

</body>
</html>
